package medium;

import java.util.ArrayList;
import java.util.List;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2021/12/4 19:44
 */
public class No54_螺旋矩阵 {
    public static void main(String[] args) {
        Solution54 solution54 = new Solution54();
        int[][] matrix = new int[][]{
              // 0   1   2   3   4   5   6
                {1,  2,  3,  4,  5,  6,  7 }, //0
                {8,  9,  10, 11, 12, 13, 14}, //1
                {15, 16, 17, 18, 19, 20, 21}, //2
                {22, 23, 24, 25, 26, 27, 28}, //3
                {29, 30, 31, 32, 33, 34, 35}, //4
        };
        List<Integer> list = solution54.spiralOrder(matrix);
        System.out.println(list);

    }
}

class Solution54 {
    public List<Integer> spiralOrder(int[][] matrix) {
        int xLength = matrix.length;
        int yLength = matrix[0].length;
        List<Integer> res = new ArrayList<>();
        // 四角龟缩大法!
        spiralOrder(matrix,
                0, 0,
                0, yLength - 1,
                xLength - 1, yLength - 1,
                xLength - 1, 0, res);

        return res;
    }

    //获取用于龟缩的4个角
    public void spiralOrder(int[][] matrix,
                            int ax, int ay,
                            int bx, int by,
                            int cx, int cy,
                            int dx, int dy,
                            List<Integer> res) {
        
        //递归终止条件
        int xmid = (matrix.length - 1) / 2;
        int ymid = (matrix[0].length - 1) / 2;
        //超出中心,毒圈炸了!返回
        if (ax > xmid || ay > ymid) {
            return;
        }
        
        //接下来大坑注意!!! 按照以上代码,如果是直线会走两轮!!
        //因此考虑只让它走一次即可
        
        //横
        if (ax == dx) {
            for (int y = ay; y <= by; y++) {
                res.add(matrix[ax][y]);
            }
            return;
        }
        
        //竖
        if (ay == by) {
            for (int x = bx; x <= cx; x++) {
                res.add(matrix[x][by]);
            }
            return;
        }
        
        
        //每个环强行4个方向遍历
        //右
        for (int y = ay; y < by; y++) {
            res.add(matrix[ax][y]);
        }
        
        //下
        for (int x = bx; x < cx; x++) {
            res.add(matrix[x][by]);
        }
        
        //左
        for (int y = cy; y > dy; y--) {
            res.add(matrix[cx][y]);
        }
        
        //上
        for (int x = dx; x > ax; x--) {
            res.add(matrix[x][dy]);
        }
        
        //下一环,四角龟缩!
        spiralOrder(matrix,
                ax + 1, ay + 1,
                bx + 1, by - 1,
                cx - 1, cy - 1,
                dx - 1, dy + 1, res);
    }
}



    //public List<Integer> spiralOrder(int[][] matrix) {
    //    //方向标
    //    //初始化方向往右侧
    //    String de = "right";
    //    List<Integer> res = new ArrayList<>();
    //    //由于一定会遍历到不能再遍历为止的那个元素,因此-1
    //    //初始化位置
    //    int x = 0;
    //    int y = 0;
    //    while (res.size() != matrix[0].length * matrix.length - 1) {
    //        //开始疯狂螺旋,遍历的顺序由方向标确定
    //        if ("right".equals(de)) {
    //            //往右遍历,如果越界,则改变
    //            if (y + 1 == matrix[0].length || matrix[x][y + 1] == -6666) {
    //                //改变方向
    //                de = "down";
    //            } else {
    //                //正常方向
    //                //不满足,加值
    //                res.add(matrix[x][y]);
    //                //走过的值,标记
    //                matrix[x][y] = -6666;
    //                y++;
    //            } 
    //        }else if ("down".equals(de)) {
    //            //往下遍历,如果越界,则改变
    //            if (x + 1 == matrix.length || matrix[x+1][y] == -6666) {
    //                //改变方向
    //                de = "left";
    //            } else {
    //                //正常方向
    //                //不满足,加值
    //                res.add(matrix[x][y]);
    //                //走过的值,标记
    //                matrix[x][y] = -6666;
    //                x++;
    //            } 
    //        }else if ("left".equals(de)) {
    //            //往左遍历,如果越界,则改变
    //            if (y - 1 < 0 || matrix[x][y - 1] == -6666) {
    //                //改变方向
    //                de = "up";
    //            } else {
    //                //正常方向
    //                //不满足,加值
    //                res.add(matrix[x][y]);
    //                //走过的值,标记
    //                matrix[x][y] = -6666;
    //                y--;
    //            }
    //        }else if ("up".equals(de)) {
    //            //往上遍历,如果越界,则改变
    //            if (x - 1 < 0 || matrix[x-1][y] == -6666) {
    //                //改变方向
    //                de = "right";
    //            } else {
    //                //正常方向
    //                //不满足,加值
    //                res.add(matrix[x][y]);
    //                //走过的值,标记
    //                matrix[x][y] = -6666;
    //                x--;
    //            }
    //        }
    //    }
    //    System.out.println();
    //
    //    //螺旋结束,++
    //    res.add(matrix[x][y]);
    //    return res;
    //}
